package william.hash;

import java.util.HashSet;
import java.util.Set;

/**
 * @author ZhangShenao
 * @date 2024/3/23
 * @description <a href="https://leetcode.cn/problems/longest-consecutive-sequence/?envType=study-plan-v2&envId=top-100-liked">...</a>
 */
public class Leetcode128_最长连续序列 {
    /**
     * 借助Hash实现
     * 首先遍历一次数组,将所有元素保存在Set中
     * 接着再次遍历数组,针对每一个元素,依次在Set中查找下一个元素,如果找到,就将最长连续序列的长度+1
     * 最后返回最长长度
     * 注意:当前数的前一个数也存在于Set中,则无需考虑当前数,等待前一个数被遍历即可,也就是每次都从序列的起始值开始考虑
     * <p>
     * 时间复杂度O(N) 需要遍历2次数组
     * 空间复杂度O(N) 额外申请了一个Hash,长度为数组长度
     */
    public int longestConsecutive(int[] nums) {
        //边界条件校验
        if (nums == null || nums.length < 1) {
            return 0;
        }

        //借助Hash保存数组元素
        Set<Integer> cache = new HashSet<>(nums.length);

        //遍历数组,将所有元素保存在Set中
        for (int n : nums) {
            cache.add(n);
        }

        //记录最长长度
        int maxLen = 0;

        //遍历数组,针对每一个元素,依次在Set中查找下一个元素,如果找到,就将最长连续序列的长度+1
        for (int i = 0; i < nums.length; i++) {
            int n = nums[i];
            if (cache.contains(n - 1)) { //当前数的前一个数也存在于Set中,则无需考虑当前数,等待前一个数被遍历即可,也就是每次都从序列的起始值开始考虑
                continue;
            }
            int len = 0;
            while (cache.contains(n)) {
                ++len;
                ++n;
            }
            maxLen = Math.max(maxLen, len);
        }

        //返回最长长度
        return maxLen;
    }
}
